As the world steams full speed ahead into the digital age, the ability to effectively search and retrieve relevant information from the ever-increasing mass of electronic data becomes more and more important. One of the most common techniques for searching for relevant textual information is performing a keyword query. A keyword query searches for documents containing one or more significant words supplied by the user. Keyword searches, however, often yield poor results because the user is forced to guess which words are important to the topic at hand. Many concepts can be described in a number of ways and relevant information may not include the keywords entered.
One technique adopted to help locate more relevant documents is the use of a similarity thesaurus. Automatic query expansion or query modification based on term co-occurrence data has been studied extensively. In a simple implementation of term co-occurrence queries, the similarities between terms are first calculated based on the association hypothesis and then used to classify terms by setting a similarity threshold value. In this way, the set of index terms is subdivided into classes of similar terms. A query is then expanded by adding all the terms of the classes that contain the query terms. Classifying terms into classes and treating the members of the same class as equivalent, however, is often too simplistic an approach to find and return relevant data.
Another search strategy is the use of document classification. In this approach, documents are first classified using a document classification algorithm. Infrequent terms found in the document class are considered similar and are clustered in the same term class, referred to as a thesaurus class. The indexing of documents and queries is enhanced either by replacing a term by a thesaurus class or by adding a thesaurus class to the index data. However, the retrieval effectiveness depends strongly on some parameters that are often difficult to determine. See, for example, C. J. Crouch, B. Young, Experiments in Automatic Statistical Thesaurus Construction, SIGIR'92, 15th Int. ACM/SIGIR Conf. on R & D in Information Retrieval, Copenhagen, Denmark, pp. 77-87, June 1992. Furthermore, commercial databases typically contain millions of documents and are highly dynamic. Often the number of documents is much larger than the number of terms in the database. Consequently, document classification is much more expensive and has to be done more frequently than the simple term classification mentioned above.
Another known method of information mining is syntactic context. In this method, term relations are generated on the basis of linguistic knowledge and co-occurrence statistics. For each term t, the method uses grammar rules and a dictionary to extract a list of terms. This list consists of all terms that modify t. The similarities between terms are then calculated by using modifiers from the list. Subsequently, a query is expanded by adding those terms most similar to any of the query terms. This produces only slightly better results than using the original queries. See, for example, G. Grefenstette, Use of Syntactic Context to Produce Term Association Lists for Retrieval, SIGIR'92, 15th Int. ACM/SIGIR Conf. on R&D in Information Retrieval, Copenhagen, Denmark, pp. 89-97, June 1992. Moreover, since there do not exist any well formed syntactic structures in multimedia data, such a technique is unsuited for multimedia query expansion.
Relevance information has been used in text retrieval as well as in multimedia retrieval. In text retrieval, relevance information can be used to construct a global information structure, such as a pseudo thesaurus or minimum spanning tree. A query is expanded by means of such a global information structure. The retrieval effectiveness of this method depends heavily on the user relevance information. Moreover, different experiments (e.g., A. F. Smeaton and C. J. van Rijsbergen, The Retrieval Effects of Query Expansion on a Feedback Document Retrieval System, The Computer Journal, 26(3):239-46, 1983) do not yield a consistent performance improvement. On the other hand, the direct use of relevance information, by simply extracting terms from relevant documents, is proved to be effective in interactive information retrieval. This approach, however, does not provide any help for queries without relevance information. An up to date summary of this technique in the context of text/document retrieval is available in G. Salton and C. Buckley, Improving Retrieval Performance by Relevance Feedback, Journal of the ASIS, 41(4):288-297, 1990.
In addition to automatic query expansion, semiautomatic query expansion has also been studied. In contrast to the fully automated methods, the user is involved in the selection of additional search terms during the semiautomatic expansion process. A list of candidate terms is computed by means of one of the methods mentioned above and presented to the user who makes the final decision. Experiments with semiautomatic query expansion, however, generally do not result in significant improvement of the retrieval effectiveness in document retrieval. See, for example, F. C. Ekmekcioglu, A. M. Robertson, Willett, Effectiveness of Query Expansion in Ranked-Output Document Retrieval Systems, Journal of Information Science, 18(2):139-47, 1992.
Relevance feedback has also been attempted in the context of video retrieval. The problem is made more difficult by the semantic gap between high-level concepts and low-level features, and the subjectivity of human perception. A comprehensive survey of relevance feedback techniques for multimedia retrieval is found in Yong Rui, Thomas S. Huang, Michael Ortega, and Sharad Mehrotra, Relevance Feedback: A Power Tool in Interactive Content-Based Image Retrieval, IEEE Tran on Circuits and Systems for Video Technology, Special Issue on Segmentation, Description, and Retrieval of Video Content, pp. 644-655, Vol. 8, No. 5, September 1998. Further specific references to this topic can be found in A. Natsev, R. Rastogi, and K. Shim, WALRUS: A Similarity Retrieval Algorithm for Image Databases, Proc. ACM SIGMOD Int. Conf. on Management of Data, 1999 and, E. Chang and B. Li, Mega—The Maximizing Expected Generalization Algorithm for Learning Complex Query Concepts (extended version), UCSB Technical Report, February 2001.
A method for learning query transformation in order to improve the ability to retrieve answers to questions from web retrieval systems has been suggested in Eugene Agichtein, Steve Lawrence, Luis Gravano, Learning Search Engine Specific Query Transformation for Question Answering, Proceedings of the Tenth International World Wide Web Conference, WWW10, May 1-5, 2001. This system automatically learns phrase features for classifying questions into different types, automatically generating candidate query transformations from a training set of questions/answer pairs, and automatically evaluating the candidate transforms on target information retrieval systems.
A probabilistic query expansion model based on a similarity thesaurus is presented in Yonggang Qiu, H. P. Frei, Concept Based Query Expansion, Proceedings of SIGIR-93, 16th International Conference on Research Development in Information Retrieval. Two issues with query expansion are addressed in this article: 1) the selection and the weighting of additional search terms; and 2) the expansion of queries by adding terms that are most similar to the concept of the query, rather than selecting terms that are similar to the query terms. A survey of probabilistic information techniques is available in Nobert Fuhr, Probabilistic Framework for Semantic Video Indexing, Filtering and Retrieval, IEEE Transactions on Multimedia, Vol. 3, No. 1, pp. 141-151, March 2001, whereas use of relevance feedback-like techniques in the context of active learning for multimedia annotation is contained in the report, M. Naphade, Ching-Yung Lin, John R. Smith, Belle Tseng, S. Basu, Learning to Annotate Video Databases, Proceedings of SPIE Storage and Retrieval for Media Databases, pp. 264-275, January 2002. None of these techniques however adequately address the problem of query expansion for multimedia retrieval based on probabilistic framework coupled with user feedback.